Token bucket · Redis-backed · 1M req/s · availability > consistency
429 + limit, remaining, reset_at{ tokens, last_filled }
Lazy refill in LUA on each request:
1. read tokens, last_filled 2. tokens += (now - last_filled) * rate tokens = min(tokens, CAPACITY) 3. if tokens >= 1: tokens -= 1 → allow else: → deny (429) 4. write back, set TTL
One atomic LUA script = no read-modify-write race.
| Algo | Trade |
|---|---|
| Fixed window | Cheap, but 2× spike at window edge |
| Sliding log | Exact, but stores every timestamp (heavy) |
| Sliding window counter | Good middle ground, approximate |
EXPIRE drops inactive user buckets after ~1h of no activity, so memory tracks active users, not all-time users.MULTI/EXEC transaction makes read → refill → decrement one indivisible step, so concurrent gateways can't race on the same bucket.isRequestAllowed — the hot-path checkisRequestAllowed(clientId, endpoint)
→ { allowed, limit,
remaining, reset_at }
allowed=false → gateway returns 429 with limit/remaining/reset_at headers; true → forward to backend.PUT /rules/:id — modify a rulePUT /rules/{ruleId}
{ scope: "user"|"ip"|"key",
limit: 50, window: "1m",
tier: "free" }
Burst: doesn't token bucket still allow ~2×?
Yes. Full bucket drained at t=0, refills over the minute, drained again near t=60 → ~200 in a 60s sliding window. The fix is lowering max CAPACITY (not the initial value — it refills back up). That's a policy dial: lower it and legit bursty clients get 429s. State it as a tradeoff, not a bug.
Hot key: one user hammers one shard
Default: gateway-local "blocked" cache. Once Redis says over-limit, cache blocked for a few seconds and stop calling Redis for that user — protects the shard. Escalation (legit whale only): split bucket into K sub-keys user:{id}:0..K-1, each capped at limit/K, pick one at random per request. Cost: remaining/reset_at must sum all K. Don't reach for splitting unless forced.
Redis dies
Fail-open (availability > consistency). Local in-memory bucket per gateway, sized limit/N for N gateways so total stays near the real limit. Choose fail-open vs fail-closed per route — open for low-risk reads, closed for expensive/write routes.
1M req/s with a Redis hop on every request
Connection pooling (skip handshake) + pipelining, Redis in same rack/region (~0.5ms RTT). Shard to spread load. Pooling does not remove the round-trip — say that explicitly.
Rules change mid-flight (100 → 50)
Grandfather existing buckets, eventual consistency is fine. Rules pushed via ZooKeeper/config, cached in gateway memory. Brief disagreement across gateways during propagation is acceptable.
Multiple rules match (user AND IP AND endpoint)
Evaluate all, enforce the most restrictive. Cost: multiple Redis ops per request (pipeline them).
reset_at with lazy refill
You store last_filled, not a window start. Compute reset_at = now + (tokens_needed / rate) — time until enough tokens refill.
Clock skew across gateways
Use the Redis server clock via TIME inside the LUA script → one authoritative clock per shard, gateway skew irrelevant.
~100 bytes/entry × 1M keys = 100 MB. Even at 10 endpoints/user → ~1 GB. Fits comfortably in RAM. Small footprint = a point in your favor.
One Redis node ≈ 100K ops/s. 1M req/s → ~10–15 shards. Consistent hashing so adding shards moves few keys.
bucket:{id}, and runs one atomic LUA script on the Redis shard for that key: read tokens, lazily refill by elapsed time, decrement if any remain. Allowed → forward; empty → 429 with reset_at. Redis sharded by user ID via consistent hashing, TTL cleans up idle keys. Rules cached in gateway memory, pushed on change. If Redis is down we fail open to a local limit/N bucket, because availability beats consistency for a limiter. Hot keys handled by a local blocked-cache, with key-splitting held in reserve for legit whales.